<html>
    <head>
    <link rel="stylesheet" href="lmm.css" type="text/css" />
    </head>
<body class="lmm">
<!-- This file is part of the Lisp Machine manual.	-*-Fundamental-*- -->
<!-- Defstruct. -->
<!-- This needs more work.  More examples are needed. -->

<div class='chapter'>4. Defstruct</div><p class='cindent' id='defstruct'><!-- structures -->
<p class='cindent'><!-- defstruct -->
<!-- Macro-defining macros!!!!! -->
<p class='cindent'><!-- macro defining macros -->

<div class='section'>4.1 Introduction to Structure Macros</div>
	<font class="lisp">defstruct</font> provides a facility in Lisp for creating and
using aggregate datatypes with named elements.  These are like
"structures" in PL/I, or "records" in PASCAL.  In the last chapter we
saw how to use macros to extend the control structures of Lisp; here we
see how they can be used to extend Lisp's data structures as well.

	To explain the basic idea, assume you were writing a Lisp
program that dealt with space ships.  In your program, you want to
represent a space ship by a Lisp object of some kind.  The interesting
things about a space ship, as far as your program is concerned, are
its position (X and Y), velocity (X and Y), and mass.  How do you
represent a space ship?

	Well, the representation could be a 5-list of the x-position,
y-position, and so on.  Equally well it could be an array of five
elements, the zeroth being the x-position, the first being the
y-position, and so on.  The  problem with both of these representations
is that the "elements" (such as x-position) occupy places in the object
which are quite arbitrary, and hard to remember (Hmm, was the mass the
third or the fourth element of the array?).  This would make programs
harder to write and read.  What we would like to see are names, easy to
remember and to understand.  If the symbol <font class="lisp">foo</font> were bound to a
representation of a space ship, then
<pre class="lisp">
(ship-x-position foo)
</pre>
could return its x-position, and
<pre class="lisp">
(ship-y-position foo)
</pre>
its y-position, and so forth.  <font class="lisp">defstruct</font> does just this.

	<font class="lisp">defstruct</font> itself is a macro which defines a structure.  For the
space ship example above, we might define the structure by saying:
<pre class="lisp">
(defstruct (ship)
     ship-x-position
     ship-y-position
     ship-x-velocity
     ship-y-velocity
     ship-mass)
</pre>

(This is a very simple case of <font class="lisp">defstruct</font>; we will see the general form
later.)  The evaluation of this form does several things.  First, it
defines <font class="lisp">ship-x-position</font> to be a macro which expands into an <font class="lisp">aref</font>
form; that is, <font class="lisp">(ship-x-position foo)</font> would turn into <font class="lisp">(aref foo 0)</font>.  All of
the "elements" are defined to refer to sequentially increasing
elements of the array, e.g., <font class="lisp">(ship-mass foo)</font> would turn into <font class="lisp">(aref foo
4)</font>.  So a ship is really implemented as an array, although that fact
is kept hidden.  These macros are called the <font class="italic">accessor macros</font>, as they
are used to access elements of the structure.

	<font class="lisp">defstruct</font> will also define <font class="lisp">make-ship</font> to be a macro which
expands into a call to <font class="lisp">make-array</font> which will create an array of the
right size (namely, 5 elements).  So <font class="lisp">(setq x (make-ship))</font> will make a
new ship, and <font class="main">x</font> will be bound to it.  This macro is called the
<font class="italic">constructor macro</font>, because it constructs a new structure.

	We also want to be able to change the contents of a structure.
To do this, we use the <font class="lisp">setf</font> macro
(see (setf-fun)), as follows (for example):
<pre class="lisp">
(setf (ship-x-position x) 100)
</pre>
Here <font class="main">x</font> is bound to a ship, and after the evaluation of the <font class="lisp">setf</font>
form, the <font class="lisp">ship-x-position</font> of that ship will be 100.  The way this
works is that the <font class="lisp">setf</font> form expands into <font class="lisp">(aset 100 x 0)</font>; again, this
is invisible to the programmer.

	By itself, this simple example provides a powerful structure
definition tool.  But, in fact, <font class="lisp">defstruct</font> has many other features.  First
of all, we might want to specify what kind of Lisp object to use for the
"implementation" of the structure.  The example above implemented a "ship"
as an array, but <font class="lisp">defstruct</font> can also implement structures as array-leaders
and as lists.  (For array-leaders, the accessor macros expand into calls
to <font class="lisp">array-leader</font>, and for lists, to <font class="lisp">car, cadr, caddr,</font> and so on.)

	Most structures are implemented as arrays.  Lists take slightly less
storage, but elements near the end of a long list are slower to access.
Array leaders allow you to have a homogeneous aggregate (the array)
and a heterogeneous aggregate with named elements (the leader) tied
together into one object.

	<font class="lisp">defstruct</font> allows you to specify to the constructor
macro what the various elements of the structure should be initialized
to.  It also lets you give, in the <font class="lisp">defstruct</font> form, default values
for the initialization of each element.

<div class='section'>4.2 Setf and Locf</div>
	In Lisp, for each function to <font class="italic">access</font> (read) any piece of
information, there is almost always a corresponding function to
<font class="italic">update</font> (write) it as well.  For example, <font class="lisp">symeval</font> accesses a
symbol's value cell, and <font class="lisp">set</font> updates it.  <font class="lisp">array-leader</font> accesses
the contents of an array leader element, and <font class="lisp">store-array-leader</font>
updates it.  The knowledge of how these functions correspond is accessible through
a macro called <font class="lisp">setf</font>.

	<font class="lisp">setf</font> is particularly useful in combination with structure-accessing
macros, such as those created with <font class="lisp">defstruct</font>, because the knowledge of the
representation of the structure is embedded inside the macro, and the programmer
shouldn't have to know what it is in order to alter an element of the structure.

<div class='defmac'><font class='exdent'><font class='funcname' id='setf'>setf</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --><br><font class="lisp">setf</font> takes a form which <font class="italic">accesses</font> something, and "inverts"
it to produce a corresponding form to <font class="italic">update</font> the thing.  The
form for <font class="lisp">setf</font> is
<pre class="lisp">
(setf <font class="italic">access-form</font> <font class="italic">value</font>)
</pre>
It expands into an update form, which stores the result of evaluating
the form <font class="italic">value</font> into the place referenced by the <font class="italic">access-form</font>.
<pre class="lisp">
<font class='exdent'>Examples:</font><!-- exdent -->
(setf (array-leader foo 3) 'bar)
		===&gt; (store-array-leader 'bar foo 3)
(setf a 3) ===&gt; (setq a 3)
(setf (plist 'a) '(foo bar)) ===&gt; (setplist 'a '(foo bar))
(setf (aref q 2) 56) ===&gt; (aset 56 q 2)
(setf (cadr w) x) ===&gt; (rplaca (cdr w) x)
</pre>
</div>

<div class='defmac'><font class='exdent'><font class='funcname' id='locf'>locf</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --><br><font class="lisp">locf</font> takes a form which <font class="italic">accesses</font> some cell, and produces
a corresponding form to create a locative pointer to that cell.
The form for <font class="lisp">locf</font> is
<pre class="lisp">
(locf <font class="italic">access-form</font>)
</pre>
<pre class="lisp">
<font class='exdent'>Examples:</font><!-- exdent -->
(locf (array-leader foo 3)) ===&gt; (ap-leader foo 3)
(locf a) ===&gt; (value-cell-location 'a)
(locf (plist 'a)) ===&gt; (property-cell-location 'a)
(locf (aref q 2)) ===&gt; (aloc q 2)
</pre>
</div>

	Both <font class="lisp">setf</font> and <font class="lisp">locf</font> work by means of property lists.
When the form <font class="lisp">(setf (aref q 2) 56)</font> is expanded, <font class="lisp">setf</font> looks
for the <font class="lisp">setf</font> property of the symbol <font class="lisp">aref</font>.  The value of the
<font class="lisp">setf</font> property of a symbol should be a <font class="italic">cons</font> whose <font class="italic">car</font>
is a pattern to be matched with the <font class="italic">access-form</font>, and whose <font class="lisp">cdr</font>
is the corresponding <font class="italic">update-form</font>, with the symbol <font class="lisp">si:val</font> in
the place of the value to be stored.  The <font class="lisp">setf</font> property of <font class="lisp">aref</font>
is a <font class="italic">cons</font> whose <font class="italic">car</font> is <font class="lisp">(aref array . subscripts)</font> and whose
<font class="italic">cdr</font> is <font class="lisp">(aset si:val array . subscripts)</font>.  If the transformation which
<font class="lisp">setf</font> is to do cannot be expressed as a simple pattern, an arbitrary
function may be used.  When the form <font class="lisp">(setf (foo bar) baz)</font>
is being expanded, if the <font class="lisp">setf</font> property of <font class="lisp">foo</font> is a symbol,
the function definition of that symbol will be applied to two arguments,
<font class="lisp">(foo bar)</font> and <font class="lisp">baz</font>, and the result will be taken to be the
expansion of the <font class="lisp">setf</font>.

Similarly, the <font class="lisp">locf</font> function
uses the <font class="lisp">locf</font> property, whose value is analogous.  For example, the <font class="lisp">locf</font> property
of <font class="lisp">aref</font> is a <font class="italic">cons</font> whose <font class="italic">car</font> is <font class="lisp">(aref array . subscripts)</font>
and whose <font class="italic">cdr</font> is <font class="lisp">(aloc array . subscripts)</font>.  There is no <font class="lisp">si:val</font>
in the case of <font class="lisp">locf</font>.

As a special case, <font class="lisp">setf</font> and <font class="lisp">locf</font> allow a variable as the reference.
In this case they turn into <font class="lisp">setq</font> and <font class="lisp">value-cell-location</font>, respectively.

	For the sake of efficiency, the code produced by <font class="lisp">setf</font> and <font class="lisp">locf</font>
does not preserve order of evaluation of the argument forms.  This is only a problem
is the argument forms have interacting side-effects.  In addition, the value produced
by <font class="lisp">setf</font> is dependant on the structure type and is not guaranteed; <font class="lisp">setf</font>
should be used for side effect only.

<div class='section'>4.3 How to Use Defstruct</div>
<div class='defmac'><font class='exdent'><font class='funcname' id='defstruct'>defstruct</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --><br>A call to <font class="lisp">defstruct</font> looks like:
<pre class="lisp">
(defstruct (<font class="italic">name</font> <font class="italic">option-1</font> <font class="italic">option-2</font> ...)
	   <font class="italic">item-1</font>
	   <font class="italic">item-2</font>
	   ...)
</pre>
<font class="italic">name</font> must be a symbol; it is the name of the structure.
It is used for many different things, explained below.

<font class="italic">option-n</font> may be either a symbol (which should be one of the recognized
option names, listed below) or a list (whose <font class="italic">car</font> should be one of the
option names and the rest of which should be "arguments" to the option).

<font class="italic">item-n</font> may be in any of three forms:
<pre class="lisp">
<font class="main">(1)</font>	<font class="italic">item-name</font>
<font class="main">(2)</font>	<font class="lisp">(<font class="italic">item-name</font> <font class="italic">default-init</font>)</font>
<font class="main">(3)</font>	((<font class="italic">item-name-1</font> <font class="italic">byte-spec-1</font> <font class="italic">default-init-1</font>)
	(<font class="italic">item-name-2</font> <font class="italic">byte-spec-2</font> <font class="italic">default-init-2</font>)
		...)
</pre>
	<font class="italic">item-name</font> must always be a symbol, and each <font class="italic">item-name</font> is
defined as an access macro.  Each <font class="italic">item</font> allocates one entry of
the physical structure, even though in form (3) several access macros
are defined.
	In form (1), <font class="italic">item-name</font> is simply defined as a macro to
return the corresponding element of the structure.  The constructor macro will
initialize that entry to <font class="lisp">nil</font> (or <font class="lisp">0</font> in a numeric array)
by default.  In form (2), the access macro
is defined the same way, but the default initialization is provided by
the user of <font class="lisp">defstruct</font>.
	In form (3), several access macros are defined, and each one
refers to the single structure element allocated for this <font class="italic">item</font>.
However, if <font class="italic">byte-spec</font> is a fixnum, the access macros will <font class="lisp">ldb</font> that
byte from the entry (see the function <font class="lisp">ldb</font>, (ldb-fun)).
<font class="italic">byte-spec</font> may also be <font class="lisp">nil</font>, in which case the usual form of
access macro is defined, returning the entire entry in the structure.
Note that it is possible to define two or more different overlapping
byte fields.  (If more than one of these has a <font class="italic">default-init</font> the
results of initializing the entry are undefined and unpredictable.)  For
example, if the third <font class="italic">item</font> of a call to <font class="lisp">defstruct</font> were
<pre class="lisp">
	((foo-high-byte 1010)
	 (foo-low-byte 0010)
	 (foo-whole-thing nil))
</pre>
then <font class="lisp">(foo-high-byte foo)</font> would expand to <font class="lisp">(ldb 1010 (aref foo
2))</font>, and <font class="lisp">(foo-whole-thing foo)</font> would expand to <font class="lisp">(aref foo 2)</font>.
	Form (3) can also be used if you want to have an element with more
than one access macro.  By putting <font class="lisp">((foo nil) (bar nil))</font>, both <font class="lisp">foo</font>
and <font class="lisp">bar</font> will be defined identically.
</div>

<div class='section'>4.4 Options to Defstruct</div>	Note that options which take no arguments may be given as just a symbol,
instead of a list.
.table 3
.item :array
The structure should be implemented as an array.  This is the default.
(No arguments.)
.item :array-leader
The structure should implemented as be an array-leader. (No arguments.)
.item :list
The structure should be implemented as a list. (No arguments.)
.item :grouped-array
See (grouped-array).
.item :times
Used by grouped arrays.  See (grouped-array).
.item :size
Takes one argument, a symbol.  The symbol gets <font class="italic">set</font> to the size of the
structure, at load-time (not compile-time).
.item :size-macro
One argument, a symbol.  The symbol gets defined as a macro,
which expands into the size of the structure.
.item :constructor
One argument, a symbol which will be the name of the constructor macro.
If the option is not present, the name of the constructor will be
made by concatenating <font class="lisp">"make-"</font> with the <font class="italic">name</font> of the structure.
If the argument is <font class="lisp">nil</font>, do not define any constructor macro.
.item :named
No argument.  This causes the constructor to
create named structure arrays (and thus may not be used with the <font class="lisp">:list</font> option)
and automatically allocate the appropriate slot in the structure and
put the name of the structure there as the named-structure symbol.
.item :default-pointer
One argument.  The access macros will be defined in such
a way that if they are called on no "arguments", the argument
to the <font class="lisp">:default-pointer</font> option will be used instead.  (Normally, access macros
will signal an error if their "argument" is missing.)
.item :make-array
One argument, arguments to the <font class="lisp">make-array</font> function.  See below.
.item :include
One argument, the name of a structure.  The structure being defined will
start out the same as that structure, with some additional elements
added at the end.
.end_table

<div class='section'>4.5 Using the Constructor Macro</div>
	If the argument to the <font class="lisp">:constructor</font> option is <font class="lisp">nil</font>, no
constructor macro is defined.  But otherwise, <font class="lisp">defstruct</font> creates a
constructor macro, which will create an instance of the
structure.  This section explains how the constructor macro interprets
its "arguments".

	A call to a constructor macro, in general, has the form
<pre class="lisp">
(<font class="italic">name-of-constructor-macro</font>
        <font class="italic">symbol-1</font> <font class="italic">form-1</font>
        <font class="italic">symbol-2</font> <font class="italic">form-2</font>
        ...)
</pre>
	Each <font class="italic">symbol</font> may be either a name of an <font class="italic">item</font> of the structure,
or a specially recognized keyword.  All <font class="italic">form</font>s are evaluated.

	If <font class="italic">symbol</font> is the name of an <font class="italic">item</font>, then that element
of the created structure will be initialized to the value of <font class="italic">form</font>.
If no <font class="italic">symbol</font> is present for a given item, then the item will be
initialized in accordance with the default initialization specified
in the call to <font class="lisp">defstruct</font>.  If the <font class="lisp">defstruct</font> itself also
did not specify any initialization, the element will be initialized
to <font class="lisp">nil</font>, unless the structure is implemented by a <font class="italic">numeric array</font>,
in which case it will be initialized to <font class="lisp">0</font>.
(In other words, the initialization specified to the constructor
overrides the initialization specified to <font class="lisp">defstruct</font>.)

	There are two symbols which are specially recognized by the
constructor.  One is <font class="lisp">:make-array</font>, which should only be used for <font class="italic">array</font>
and <font class="italic">array-leader</font> type structures.  The value of <font class="italic">form</font> is used as the
argument list to the <font class="lisp">make-array</font> function call created by the constructor.
This way, you can specify the area in which you wish the structure to
be created, the type of the array to be created, and so on.  Of
course, if you provided <font class="italic">all</font> of the arguments to <font class="lisp">make-array</font>, the
constructor would not be able to do its job; so the constructor overrides
your specifications of certain elements.  If the structure is <font class="italic">array</font>
type, your specification of the array's dimensions (the third argument to
<font class="lisp">make-array</font>) is ignored; if it is of <font class="italic">array-leader</font> type, the array-leader
argument (the fifth argument to <font class="lisp">make-array</font>) is ignored.  Also, in both
cases the named-structure argument (the seventh argument to
<font class="lisp">make-array</font>) is ignored.  They are ignored because it is the constructor
macro's job to fill them in.  If the list you provide is shorter than the number
of arguments to <font class="lisp">make-array</font>, it will be as if you had given the missing
elements as <font class="lisp">nil</font>.  Similarly, if your list is too long, the extra elements
will be ignored.  If you do not provide the <font class="lisp">:make-array</font> keyword
at all, the arguments default from the value of the <font class="lisp">:make-array</font>
option to <font class="lisp">defstruct</font>.  If you did not even provide that, the
default argument lists are:

.table 1
.item For <font class="italic">array</font>s:
<font class="lisp">(default-array-area 'art-q <font class="italic">whatever</font> nil nil nil <font class="italic">whatever</font>)</font>
.item For <font class="italic">array-leader</font>s:
<font class="lisp">(default-array-area 'art-q  0 nil <font class="italic">whatever</font> nil <font class="italic">whatever</font>)</font>
.end_table
	The second keyword recognized by the constructor is <font class="lisp">:times</font>,
which should only be used for <font class="lisp">grouped-arrays</font>.  Its value is the number
of repetitions of the structure in the grouped-array.  If <font class="lisp">:times</font> is not
provided, it defaults from the <font class="lisp">:times</font> option of <font class="lisp">defstruct</font>.  If you did
not even provide that, the default is 1.

<div class='section'>4.6 Grouped Arrays</div>	The grouped array feature allows you to store several
instances of a structure side-by-side within an array.  This feature
is somewhat limited, and requires that the structure be implemented as an array,
that it not have any <font class="lisp">:include</font> option, and that it not be a
named structure.

	The accessor macros are defined to take a "first argument" which
should be a fixnum, and is the index into the array of where this
instance of the structure starts.  It should be a multiple of the size
of the structure, for things to make sense.

	Note that the "size" of the structure (as given in the <font class="lisp">:size</font> symbol
and the <font class="lisp">:size-macro</font>) is the number of elements in <font class="italic">one</font> instance of the structure;
the actual length of the array is the product of the size of the structure and the
number of instances.  The number of instances to be created by the creator
macro is given as the argument to the <font class="lisp">:times</font> or <font class="lisp">:grouped-array</font> option, or 
the <font class="lisp">:times</font> keyword of the constructor macro (see below).

<div class='section'>4.7 Grouped Arrays</div>
<p class='cindent' id='named-structure'><!-- named-structure -->

	The <font class="italic">named structure</font> feature provides a very simple form of
user-defined data type.  Any array may be made a named structure, although
usually the <font class="lisp">:named</font> option of <font class="lisp">defstruct</font> is used to create named
structures.  The principle advantages to a named structure are that it has
a more informative printed representation than a normal array and that
the <font class="lisp">describe</font> function knows how to give a detailed description of it.
Because of these improved user-interface features it is recommended that
"system" data structures be implemented with named structures.

	Another kind of user-defined data type, more advanced but less
efficient, is provided by the <font class="italic">actor</font> feature (see (actor)).

	A named structure has an associated symbol, called its "named
structure symbol", which represents what user-defined type it is an
instance of; the <font class="lisp">typep</font> function, applied to the named structure,
will return this symbol.  If the array has a leader, then the symbol is
found in element 1 of the leader; otherwise it is found in element 0 of
the array.  (Note: if a numeric-type array is to be a named structure,
it must have a leader, since a symbol cannot be stored in any element
of a numeric array.)

	The named structure symbol should be defined as a function.  The functions
which know about named structures will apply this function to
several arguments. The first is a "keyword" symbol to
identify the calling function, and the second is the named structure
itself.  The rest of the arguments passed depend on the caller; any
named structure function should have a "<font class="lisp">&rest</font>" parameter to
absorb any extra arguments that might be passed.  Just what
the function is expected to do depends on the keyword it is passed
as its first argument.  The following are the keywords defined at present:
.table 3
.item :which-operations
Should return a list of the names of the operations the function handles.
.item :print
The arguments are <font class="lisp">:print</font>, the named structure, the stream to output to,
the current depth in
list-structure, and <font class="lisp">t</font> if slashification is enabled (<font class="lisp">prin1</font>
versus <font class="lisp">princ</font>).  The printed representation of the named structure
should be output to the stream.  If the named structure symbol
is not defined as a function, or <font class="lisp">:print</font> is not in its
<font class="lisp">:which-operations</font> list, the printer will default to a reasonable
printed representation.
.item :describe
The arguments are <font class="lisp">:describe</font> and the named structure.  It should
output a description of itself to <font class="lisp">standard-output</font>.  If the named
structure symbol is not defined as a function, or <font class="lisp">:describe</font> is not
in its <font class="lisp">:which-operations</font> list, the describe system will
check whether the named structure was created by using the <font class="lisp">:named</font>
option of <font class="lisp">defstruct</font>; if so, the names and values of the structure's
fields will be enumerated.
.end_table

The following functions operate on named structures.

<div class='defun'><font class='exdent'><font class='funcname'>named-structure-p <font class='italic' color='purple'>x</font></font></font><br>
This predicate returns <font class="lisp">t</font> if <font class="italic">x</font> is a named structure; otherwise
it returns <font class="lisp">nil</font>.
</div>

<div class='defun'><font class='exdent'><font class='funcname'>named-structure-symbol <font class='italic' color='purple'>x</font></font></font><br>
<font class="italic">x</font> should be a named structure.  This returns <font class="italic">x</font>'s named structure
symbol: if <font class="italic">x</font> has an array leader, element 1 of the leader is returned,
otherwise element 0 of the array is returned.
</div>

<div class='defun'><font class='exdent'><font class='funcname'>make-array-into-named-structure <font class='italic' color='purple'>array</font></font></font><br>
<font class="italic">array</font> is made to be a named structure, and is returned.
</div>

<div class='defun'><font class='exdent'><font class='funcname'>named-structure-invoke <font class='italic' color='purple'>str op &rest args</font></font></font><br>
<font class="italic">str</font> should be a named structure, and <font class="italic">op</font> should be a keyword
symbol.  The function definition of the named structure symbol is called
with appropriate arguments.
</div>

.eof
</body>
</html>

